home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / fax / src / util / Array.c++ next >
C/C++ Source or Header  |  1994-08-01  |  8KB  |  365 lines
  1. /*    $Header: /usr/people/sam/fax/util/RCS/Array.c++,v 1.11 1994/02/28 14:24:05 sam Rel $ */
  2. /*
  3.  * Copyright (c) 1990, 1991, 1992, 1993, 1994 Sam Leffler
  4.  * Copyright (c) 1991, 1992, 1993, 1994 Silicon Graphics, Inc.
  5.  *
  6.  * Permission to use, copy, modify, distribute, and sell this software and 
  7.  * its documentation for any purpose is hereby granted without fee, provided
  8.  * that (i) the above copyright notices and this permission notice appear in
  9.  * all copies of the software and related documentation, and (ii) the names of
  10.  * Sam Leffler and Silicon Graphics may not be used in any advertising or
  11.  * publicity relating to the software without the specific, prior written
  12.  * permission of Sam Leffler and Silicon Graphics.
  13.  * 
  14.  * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 
  15.  * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 
  16.  * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.  
  17.  * 
  18.  * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
  19.  * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
  20.  * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  21.  * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF 
  22.  * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE 
  23.  * OF THIS SOFTWARE.
  24.  */
  25. #include "Array.h"
  26. #include <stdlib.h>
  27.  
  28. #define that (*this)
  29.  
  30. fxArray::fxArray(u_short esize, u_int initlength)
  31. {
  32.     num = maxi = initlength * esize;
  33.     elementsize = esize;
  34.     if (maxi != 0)
  35.     data = malloc((u_int) maxi);
  36.     else
  37.     data = 0;
  38.     // Don't create the elements because the subclass will do that, because
  39.     // we can't call a virtual from within this constructor.
  40. }
  41.  
  42. fxArray::fxArray(const fxArray & other)
  43. {
  44.     num = other.num;
  45.     maxi = other.num;
  46.     elementsize = other.elementsize;
  47.     data = 0;
  48.     getmem();
  49.     copyElements(other.data,data,num);
  50. }
  51.  
  52. fxArray::fxArray(u_int esize, u_int n, void * d)
  53. {
  54.     elementsize=esize;
  55.     num=maxi=n;
  56.     data=d;
  57. }
  58.  
  59. fxArray::~fxArray()
  60. {
  61.     delete (void*)data;
  62. }
  63.  
  64. void
  65. fxArray::destroy()
  66. {
  67.     if (num != 0) destroyElements(data,num);
  68. }
  69.  
  70. u_int fxArray::length() const { return num/elementsize; }
  71.  
  72. void
  73. fxArray::append(void const * item) {
  74.     assert(num<=maxi);
  75.     if (num == maxi) expand();
  76.     copyElements(item, data + num, elementsize);
  77.     num += elementsize;
  78. }
  79.  
  80. void
  81. fxArray::append(const fxArray & a) {
  82.     assert(elementsize == a.elementsize);
  83.     u_int length = a.num;
  84.     if (length > 0) {
  85.     if (num + length > maxi) {
  86.         maxi = num + length;
  87.         getmem();
  88.     }
  89.     copyElements(a.data, data+num, length);
  90.     num += length;
  91.     }
  92. }
  93.  
  94. void
  95. fxArray::remove(u_int start, u_int length) {
  96.   if (length>0) {
  97.     start *= elementsize;
  98.     length *= elementsize;
  99.     assert(start+length <= num);
  100.     destroyElements(data+start,length);
  101.     if (start+length < num) {
  102.     memmove((void*)(data + start),
  103.         (void*)(data + start+length), num - (start+length));
  104.     // we don't use copyElements because they are just being moved.
  105.     }
  106.     num -= length;
  107.     // we don't destroy the end elements because they still exist; they've
  108.     // just been moved.
  109.   }
  110. }
  111.  
  112. void
  113. fxArray::resize(u_int length) {
  114.     length *= elementsize;
  115.     maxi = length;
  116.     if (length>num) {
  117.     getmem();
  118.     createElements(data + num, length - num);
  119.     } else if (num>length) {
  120.     destroyElements(data + length, num - length);
  121.     getmem();
  122.     }
  123.     num = length;
  124. }
  125.  
  126. void
  127. fxArray::setMaxLength(u_int length)
  128. {
  129.     length *= elementsize;
  130.     length = fxmax(length,num);
  131.     if (maxi != length) {
  132.     maxi = length;
  133.     getmem();
  134.     }
  135. }
  136.  
  137. void
  138. fxArray::createElements(void*, u_int)
  139. {
  140. }
  141.  
  142. void
  143. fxArray::destroyElements(void*, u_int)
  144. {
  145. }
  146.  
  147. void
  148. fxArray::copyElements(const void * source, void * dest, u_int length) const
  149. {
  150.     memmove(dest,source,length);
  151. }
  152.  
  153. int
  154. fxArray::compareElements(const void * e1, const void * e2) const
  155. {
  156.     return memcmp(e1,e2,elementsize);
  157. }
  158.  
  159. void
  160. fxArray::expand()
  161. { // by default, grab 4 more element spaces
  162.     maxi += elementsize*4;
  163.     getmem();
  164. }
  165.  
  166. // this function keeps `data' up to date when maxi has just been changed
  167. void
  168. fxArray::getmem()
  169. {
  170.     if (maxi == 0) {
  171.     delete (void*)data;
  172.     data = 0;
  173.     } else {
  174.     if (data)
  175.         data = realloc(data,maxi);
  176.     else
  177.         data = malloc(maxi);
  178.     }
  179. }
  180.  
  181. void
  182. fxArray::insert(fxArray const & a, u_int posn)
  183. {
  184.     u_int length = a.num;
  185.     if (a.length()>0) {
  186.     assert(elementsize == a.elementsize);
  187.     posn *= elementsize;
  188.     assert(posn <= num);
  189.     if (maxi < num + length) {
  190.         maxi = num + length;
  191.         getmem();
  192.     }
  193.     if (posn < num) {
  194.         memmove((void*)(data+posn+length), (void*)(data+posn), num-posn);
  195.         // we don't need to do a copyElements because we're not
  196.         // making new copies of objects, we're just moving
  197.         // existing ones.
  198.     }
  199.     copyElements(a.data, data+posn, length);
  200.     num += length;
  201.     }
  202. }
  203.  
  204. void
  205. fxArray::insert(void const * item, u_int posn)
  206. {
  207.     posn *= elementsize;
  208.     assert(posn <= num);
  209.     if (maxi <= num) {
  210.     maxi = num+elementsize;
  211.     getmem();
  212.     }
  213.     if (posn<num) {
  214.     memmove((void*)(data+posn+(u_int)elementsize),
  215.         (void*)(data+posn), num-posn);
  216.     }
  217.     copyElements(item, data+posn, elementsize);
  218.     num += elementsize;
  219. }
  220.  
  221. #define TEMPSIZE 1024
  222.  
  223. void
  224. fxArray::swap(u_int p1, u_int p2)
  225. {
  226.     char buffer[TEMPSIZE];
  227.     void *tmp;
  228.     p1 *= elementsize;
  229.     p2 *= elementsize;
  230.     if (elementsize>TEMPSIZE) tmp=malloc(elementsize);
  231.     else tmp = buffer;
  232.     memcpy(tmp,(void*)(data+p1),elementsize);
  233.     memcpy((void*)(data+p1),(void*)(data+p2),elementsize);
  234.     memcpy((void*)(data+p2),tmp,elementsize);
  235. }
  236.  
  237. u_int
  238. fxArray::find(void const * item, u_int start) const
  239. {
  240.     assert(start*elementsize <= num);
  241.     fxAddress p = data + (u_int)(start*elementsize);
  242.     while (p < data + num) {
  243.     if (0 == compareElements(item,p)) return start;
  244.     p = p+elementsize;
  245.     start++;
  246.     }
  247.     return fx_invalidArrayIndex;
  248. }
  249.  
  250. void
  251. fxArray::qsortInternal(u_int l, u_int r, void * tmp)
  252. {
  253.     register u_int i=l;
  254.     register u_int k=r+1;
  255.     u_int e = elementsize;
  256.  
  257.     assert(k<=length());
  258.  
  259.     void * item = that[l];
  260.  
  261.     for (;;) {
  262.     for (;;) {
  263.             if(i>=r)break;
  264.             ++i;
  265.             if (compareElements(that[i],item) >= 0) break;
  266.         }
  267.         for (;;) {
  268.             if (k<=l) break;
  269.             --k;
  270.             if (compareElements(that[k],item) <= 0) break;
  271.         }
  272.         if (i>=k) break;
  273.  
  274.     memcpy(tmp,that[i],e);
  275.     memcpy(that[i],that[k],e);
  276.     memcpy(that[k],tmp,e);
  277.     }
  278.     memcpy(tmp,that[l],e);
  279.     memcpy(that[l],that[k],e);
  280.     memcpy(that[k],tmp,e);
  281.     if (k && l<k-1) qsortInternal(l,k-1,tmp);
  282.     if (k+1 < r) qsortInternal(k+1,r,tmp);
  283. }
  284.  
  285. #define SMALLBUFFERSIZE 32
  286.  
  287. void
  288. fxArray::qsort(u_int posn, u_int len)
  289. {
  290.     if (len == 0) return;
  291.     char smallbuffer[SMALLBUFFERSIZE];
  292.     assert(posn+len <= num);
  293.     void *tmp = (elementsize > SMALLBUFFERSIZE)
  294.     ? malloc(elementsize)
  295.     : smallbuffer;
  296.     qsortInternal(posn,posn+len-1,tmp);
  297.     if (tmp != smallbuffer) delete tmp;
  298. }
  299.  
  300. void
  301. fxArray::qsort()
  302. {
  303.     qsort(0,length());
  304. }
  305.  
  306. void *
  307. fxArray::raw_extract(u_int start, u_int len) const
  308. {
  309.     if (len == 0) return 0;
  310.     start *= elementsize;
  311.     len *= elementsize;
  312.     assert(start+len<=num);
  313.     void * ret = malloc(len);
  314.     copyElements(data+start, ret, len);
  315.     return ret;
  316. }
  317.  
  318. void *
  319. fxArray::raw_cut(u_int start, u_int len)
  320. {
  321.     if (len == 0) return 0;
  322.     start *= elementsize;
  323.     len *= elementsize;
  324.     assert(start+len <= num);
  325.     void * ret = malloc(len);
  326.     // we don't copy because we aren't making copies, we're just
  327.     // moving existing elements from one array to another.
  328.     memcpy(ret, (void*)(data+start), len);
  329.     if (start+len < num) {
  330.     // we don't use copyElements because they are just being moved.
  331.     memmove((void*)(data + start),
  332.         (void*)(data + start+len), num - (start+len));
  333.     }
  334.     num -= len;
  335.     return ret;
  336. }
  337.  
  338. void *
  339. fxArray::raw_copy() const
  340. {
  341.     if (num == 0) return 0;
  342.     void * ret = malloc(num);
  343.     copyElements(data,ret,num);
  344.     return ret;
  345. }
  346.  
  347. void *
  348. fxArray::raw_head(u_int len) const
  349. {
  350.     if (len == 0) return 0;
  351.     assert(len <= num);
  352.     return raw_extract(0,len);
  353. }
  354.  
  355. void *
  356. fxArray::raw_tail(u_int len) const
  357. {
  358.     if (len == 0) return 0;
  359.     len *= elementsize;
  360.     assert(len <= num);
  361.     void * ret = malloc(len);
  362.     copyElements(data+(num-len), ret, len);
  363.     return ret;
  364. }
  365.